#ifndef DTREE_H_INCLUDED
#define DTREE_H_INCLUDED

#include "headers.h"

using namespace std;

struct TreeNode
{
    int _ID;    // vid: 0, 1, ..., N-1 for N vertices
   int _IntBeg;
    int _IntEnd;
    int _PreN;
    int _LmdID;   // ID left-most descendant
    bool _visited;
    struct TagRange
    {
        int _start, _end;
    } _RangeSNTE;
};

typedef vector<int> Children;
typedef vector<TreeNode> TreeNodeList;


struct FatherSonList
{
    int _father;
    Children _sons;
};
typedef vector<FatherSonList> TREE;

class DTree
{
private:
    TREE _T;
    TreeNodeList _VL;
    int _N; // number of vertices
    vector<int> roots;
 //   int _M; // number of edges

public:
    DTree();
    DTree(int N);
    DTree(istream& in);

    ~DTree();

    void clear();

    void add_vertex(int vid);
    bool remove_vertex(int vid);
    bool add_edge(int src, int trg);
    bool remove_edge(int src, int trg);
    int number_of_vertices();
    int number_of_edges();
    TreeNodeList& get_vertices();
    Children& children_of(int vid);
    int father_of(int vid);

    int out_degree_of(int vid);
    int in_degree_of(int vid);

    void write_tree(ostream& out);

    vector<int> get_roots();
    bool has_edge(int src, int trg);
    DTree& operator=(const DTree& tree);
    TreeNode& operator[](const int vid);
void addRoots(int root);
};

#endif // DTREE_H_INCLUDED
